๐Ÿ‘ฉโ€๐Ÿ’ป 81305. ์‹œํ—˜์žฅ ๋‚˜๋ˆ„๊ธฐ

@Seongukbaek Posted May 06, 2022 ยท Updated May 06, 2022 ยท 6 min read

๋ฌธ์ œ

Programmers - ์‹œํ—˜์žฅ ๋‚˜๋ˆ„๊ธฐ

๐Ÿ“ Logic

private int dfs(int cur, int limit) { // ์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ ์ž์‹ ํŠธ๋ฆฌ์—์„œ ๋„˜์–ด์˜ค๋Š” ์ธ์› ์ˆ˜ int leftValue = 0, rightValue = 0; if (left[cur] != -1) leftValue = dfs(left[cur], limit); if (right[cur] != -1) rightValue = dfs(right[cur], limit); // ๋‘ ์ž์‹ ํŠธ๋ฆฌ์—์„œ ๋„˜์–ด์˜ค๋Š” ์ธ์›์„ ๋ชจ๋‘ ๊ฐ๋‹นํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ, ๊ทธ๋ฃน ์ˆ˜๋Š” ์ฆ๊ฐ€ํ•˜์ง€ ์•Š์Œ if (x[cur] + leftValue + rightValue <= limit) return x[cur] + leftValue + rightValue; // ๋‘ ์ž์‹ ํŠธ๋ฆฌ ์ค‘ ์ž‘์€ ๊ฐ’์„ ํ•ฉ์ณ์•ผ ๊ฐ๋‹นํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ, ์ฆ‰ ์ž์‹ ๋…ธ๋“œ ํ•˜๋‚˜๋ฅผ ๋Š๋Š” ๊ฒฝ์šฐ๋กœ ๊ทธ๋ฃน์ด 1๊ฐœ ์ถ”๊ฐ€ if (x[cur] + Math.min(leftValue, rightValue) <= limit) { count++; return x[cur] + Math.min(leftValue, rightValue); } // ๋‘ ์ž์‹ ํŠธ๋ฆฌ ๋ชจ๋‘ ๊ฐ๋‹นํ•  ์ˆ˜ ์—†์–ด์„œ ๋‘˜ ๋‹ค ๋Š๋Š” ๊ฒฝ์šฐ, ๊ทธ๋ฃน์ด 2๊ฐœ ์ถ”๊ฐ€ count += 2; return x[cur]; }
  • ์ฃผ์–ด์ง„ ํŠธ๋ฆฌ์—์„œ ๊ฐ ๊ทธ๋ฃน์˜ ์ˆ˜๋ฅผ x๋ช…์œผ๋กœ ์ œํ•œํ•  ๋•Œ ํ•„์š”ํ•œ ๊ทธ๋ฃน์˜ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•ด์•ผ ํ•œ๋‹ค.
  • ๊ฐ ๊ทธ๋ฃน์˜ ์ˆ˜๋ฅผ x๋ช…์œผ๋กœ ์ œํ•œํ•  ๋•Œ ํ•„์š”ํ•œ ๊ทธ๋ฃน์˜ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๊ธฐ ์œ„ํ•ด ๊ทธ๋ฆฌ๋””๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ตœ๋Œ€ํ•œ ๊ทธ๋ฃน ์ƒ์„ฑ์„ ๋ฏธ๋ฃจ๋ฉด์„œ ์œ„๋กœ ์˜ฌ๋ ค๋ณด๋‚ธ๋‹ค.

    • ๋ถ€๋ชจ ๋…ธ๋“œ์—์„œ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๋” ์ด์ƒ ๊ฐ๋‹นํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ, ๊ฐ’์ด ๋” ์ž‘์€ ๋…ธ๋“œ๋ฅผ ์ฑ™๊ธฐ๊ณ  ๋‹ค๋ฅธ ๋…ธ๋“œ๋ฅผ ์ž˜๋ผ๋‚ธ๋‹ค.
  • ๊ทธ๋ฃน์œผ๋กœ ๋‚˜๋ˆŒ ๋•Œ ์•„๋ž˜ 3๊ฐ€์ง€ ๊ฒฝ์šฐ๊ฐ€ ์กด์žฌํ•œ๋‹ค.

    • ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ์ž์‹ ๋…ธ๋“œ ๋ชจ๋‘ ์ฑ™๊ธฐ๊ธฐ : ๊ทธ๋ฃน + 0, ์„ธ ๋…ธ๋“œ์˜ ํ•ฉ์„ ๋” ๋ถ€๋ชจ ๋…ธ๋“œ๋กœ ์ „๋‹ฌ
    • ์ž์‹ ๋…ธ๋“œ ์ค‘ 1๊ฐœ์™€ ๋ถ€๋ชจ ๋…ธ๋“œ๋ฅผ ์ฑ™๊ธฐ๊ธฐ : ๊ทธ๋ฃน + 1, ์ž์‹ ๋…ธ๋“œ ์ค‘ ์ตœ์†Ÿ๊ฐ’ + ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ๊ฐ’์„ ๋” ๋ถ€๋ชจ ๋…ธ๋“œ๋กœ ์ „๋‹ฌ
    • ์ž์‹ ๋…ธ๋“œ๋ฅผ ํ•˜๋‚˜๋„ ์ฑ™๊ธฐ์ง€ ์•Š๊ธฐ : ๊ทธ๋ฃน + 2, ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ๊ฐ’๋งŒ ๋” ๋ถ€๋ชจ ๋…ธ๋“œ๋กœ ์ „๋‹ฌ
  • DFS๋ฅผ ํ†ตํ•ด ๋ฆฌํ”„ ๋…ธ๋“œ๋ถ€ํ„ฐ ๊ฐ’์„ ์œ„๋กœ ์˜ฌ๋ ค๋ณด๋‚ด๋Š” ์ž‘์—…์„ ๋ฐ˜๋ณตํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class ExamRoom { int n; int root; int count = 0; int[] left; int[] right; int[] x; // ์‹œํ—˜์žฅ์˜ ์‘์‹œ ์ธ์› int[] parent; public ExamRoom(int[] num, int[][] links) { this.n = num.length; parent = new int[n]; left = new int[n]; right = new int[n]; x = new int[n]; Arrays.fill(parent, -1); init(num, links); setRoot(); } private void init(int[] num, int[][] links) { for (int i = 0; i < n; i++) { int l1 = links[i][0]; int l2 = links[i][1]; // ์ž์‹ ์ง€์ • left[i] = l1; right[i] = l2; x[i] = num[i]; // ๋ถ€๋ชจ ์ง€์ • if (l1 != -1) parent[left[i]] = i; if (l2 != -1) parent[right[i]] = i; } } // parent[i]๊ฐ€ -1์ด๋ผ๋ฉด root private void setRoot() { for (int i = 0; i < n; i++) { if (parent[i] == -1) { root = i; return; } } } public int getAnswer(int k) { // start๋Š” num์˜ ์ตœ๋Œ“๊ฐ’ int start = x[0]; for (int i : x) start = Math.max(start, i); // end๋Š” num์˜ ์ตœ๋Œ“๊ฐ’ * num์˜ ๊ธธ์ด int end = start * n; while(start < end) { int mid = (start + end) / 2; if (solve(mid) <= k) end = mid; else start = mid + 1; } return start; } private int solve(int limit) { count = 0; dfs(root, limit); // ๋งจ ๋งˆ์ง€๋ง‰์— ๋‚จ์€ ์ธ์›๋“ค์— ๋Œ€ํ•œ ๊ทธ๋ฃน ํ•˜๋‚˜ ์ถ”๊ฐ€ return count + 1; } private int dfs(int cur, int limit) { // ์™ผ์ชฝ๊ณผ ์˜ค๋ฅธ์ชฝ ์ž์‹ ํŠธ๋ฆฌ์—์„œ ๋„˜์–ด์˜ค๋Š” ์ธ์› ์ˆ˜ int leftValue = 0, rightValue = 0; if (left[cur] != -1) leftValue = dfs(left[cur], limit); if (right[cur] != -1) rightValue = dfs(right[cur], limit); // ๋‘ ์ž์‹ ํŠธ๋ฆฌ์—์„œ ๋„˜์–ด์˜ค๋Š” ์ธ์›์„ ๋ชจ๋‘ ๊ฐ๋‹นํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ, ๊ทธ๋ฃน ์ˆ˜๋Š” ์ฆ๊ฐ€ํ•˜์ง€ ์•Š์Œ if (x[cur] + leftValue + rightValue <= limit) return x[cur] + leftValue + rightValue; // ๋‘ ์ž์‹ ํŠธ๋ฆฌ ์ค‘ ์ž‘์€ ๊ฐ’์„ ํ•ฉ์ณ์•ผ ๊ฐ๋‹นํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ, ์ฆ‰ ์ž์‹ ๋…ธ๋“œ ํ•˜๋‚˜๋ฅผ ๋Š๋Š” ๊ฒฝ์šฐ๋กœ ๊ทธ๋ฃน์ด 1๊ฐœ ์ถ”๊ฐ€ if (x[cur] + Math.min(leftValue, rightValue) <= limit) { count++; return x[cur] + Math.min(leftValue, rightValue); } // ๋‘ ์ž์‹ ํŠธ๋ฆฌ ๋ชจ๋‘ ๊ฐ๋‹นํ•  ์ˆ˜ ์—†์–ด์„œ ๋‘˜ ๋‹ค ๋Š๋Š” ๊ฒฝ์šฐ, ๊ทธ๋ฃน์ด 2๊ฐœ ์ถ”๊ฐ€ count += 2; return x[cur]; } } class Solution { public int solution(int k, int[] num, int[][] links) { ExamRoom er = new ExamRoom(num, links); return er.getAnswer(k); } }

โœ๏ธ Review

  • ์ฒ˜์Œ ๋ณด๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜๋Š” ๋ฌธ์ œ์—ฌ์„œ ์ฐธ๊ณ ๋ฅผ ์ฐฌ์ฐฌํžˆ ์ฝ์–ด๋ณด๋ฉด์„œ ์ดํ•ดํ•˜๋ ค๊ณ  ํ–ˆ๋‹ค.
  • ๊ฐ ๊ทธ๋ฃน์˜ ์ˆ˜๋ฅผ x๋ช…์œผ๋กœ ์ œํ•œํ•  ๋–„ ๊ทธ๋ฃน์˜ ์ˆ˜๊ฐ€ k๊ฐœ ์ดํ•˜์ธ์ง€๋ฅผ ํŒ๋‹จํ•˜๋Š” ๊ฒฐ์ • ๋ฌธ์ œ ์ฆ‰, Parametric Search๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๋ฌธ์ œ๋ฅผ ์ฒ˜์Œ ์ ‘ํ•œ ๊ฒƒ ๊ฐ™๋‹ค... ๋ฌธ์ œ๋ฅผ ๋‹ค์–‘ํ•˜๊ฒŒ ํ’€์–ด๋ณผ ์ˆ˜ ์žˆ์–ด์•ผ ๊ฒ ๋‹ค.

๐Ÿ“• ์ฐธ๊ณ 

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์‹œํ—˜์žฅ ๋‚˜๋ˆ„๊ธฐ / 2021 ์นด์นด์˜ค ์ฑ„์šฉ์—ฐ๊ณ„ํ˜• ์ธํ„ด์‹ญ - JAVA

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€